package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.NextNode;
import com.algorithm.liyc.entity.Node;
import com.algorithm.liyc.entity.TreeNode;

import java.util.*;

/**
 * 二叉树的层序遍历
 * 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
 * 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
 * 而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
 *
 * @author Liyc
 * @date 2023/12/27 16:12
 **/

public class Solution4 {

    /**
     * 102.二叉树的层序遍历
     * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> integerList = new ArrayList<>();
            int len = queue.size();

            while (len > 0) {
                TreeNode node = queue.poll();
                integerList.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                len--;

            }
            result.add(integerList);
        }
        return result;
    }

    /**
     * 107.二叉树的层次遍历 II
     * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     * 思路和模板相同, 对收集答案的方式做了优化, 最后不需要反转
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 利用链表可以进行 O(1) 头部插入, 这样最后答案不需要再反转
        LinkedList<List<Integer>> result = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> integerList = new ArrayList<>();
            int len = queue.size();

            while (len > 0) {
                TreeNode node = queue.poll();
                integerList.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                len--;

            }
            // 新遍历到的层插到头部, 这样就满足按照层次反序的要求
            result.addFirst(integerList);
        }
        return result;
    }

    /**
     * 199.二叉树的右视图
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     * 解法：队列，迭代。
     * 每次返回每层的最后一个字段即可。
     * 小优化：每层右孩子先入队。代码略
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();

            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.pollFirst();
                if (treeNode.left != null) deque.addLast(treeNode.left);
                if (treeNode.right != null) deque.addLast(treeNode.right);

                if (i == size - 1) {
                    result.add(treeNode.val);
                }
            }
        }
        return result;
    }

    /**
     * 637.二叉树的层平均值
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
     * 解法：队列，迭代。
     * 每次返回每层的最后一个字段即可。
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            double temp = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.pollFirst();
                temp += treeNode.val;
                if (treeNode.left != null) deque.addLast(treeNode.left);
                if (treeNode.right != null) deque.addLast(treeNode.right);
            }
            result.add(temp / size);
        }
        return result;
    }

    /**
     * 429.N叉树的层序遍历
     * 给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Node> deque = new LinkedList<>();
        if (root == null) {
            return result;
        }
        deque.offerLast(root);
        while (!deque.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int len = deque.size();

            for (int i = 0; i < len; i++) {
                Node node = deque.pollLast();
                levelList.add(node.val);
                List<Node> children = node.children;
                if (children == null || children.size() == 0) {
                    continue;
                }
                for (Node node1 : children) {
                    if (node1 != null) {
                        deque.addLast(node1);
                    }
                }
            }
            result.add(levelList);
        }
        return result;
    }

    /**
     * 515.在每个树行中找最大值
     * 您需要在二叉树的每一行中找到最大的值。
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) {
            return result;
        }
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.pollFirst();
                max = Math.max(max, treeNode.val);
                if (treeNode.left != null) deque.addLast(treeNode.left);
                if (treeNode.right != null) deque.addLast(treeNode.right);
            }
            result.add(max);
        }
        return result;
    }

    /**
     * 116.填充每个节点的下一个右侧节点指针
     * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * @param root
     * @return
     */
    public NextNode connect(NextNode root) {
        Queue<NextNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            NextNode cur = queue.poll();
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);

            for (int i = 1; i < size; i++) {
                NextNode next = queue.poll();
                if (next.left != null) queue.offer(next.left);
                if (next.right != null) queue.offer(next.right);
                cur.next = next;
                cur = next;
            }
        }
        return root;
    }

    /**
     * 117.填充每个节点的下一个右侧节点指针II
     * 这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道
     * @param root
     * @return
     */
    public NextNode connect2(NextNode root) {
        Queue<NextNode> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            NextNode node = null;
            NextNode nodePre = null;

            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = queue.poll(); // 取出本层头一个节点
                    node = nodePre;
                } else {
                    node = queue.poll();
                    nodePre.next = node; // 本层前一个节点 next 指向当前节点
                    nodePre = nodePre.next;
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            nodePre.next = null; // 本层最后一个节点 next 指向 null
        }
        return root;
    }

    /**
     * 104.二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 说明: 叶子节点是指没有子节点的节点。
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return depth;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();

            while (len > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                len--;

            }
            depth++;
        }
        return depth;
    }

    /**
     * 111.二叉树的最小深度
     * 相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。
     * 需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return depth;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            depth++;
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

        }
        return depth;
    }
}
